      1  /**

      2     The sort method of this class sorts an array, using the merge

      3     sort algorithm.

      4  */

      5  public class MergeSorter

      6  {

      7     /**

      8        Sorts an array, using merge sort.

      9        @param a the array to sort

     10     */

     11     public static void sort(int[] a)

     12     {

     13        if (a.length <= 1) { return; }

     14        int[] first = new int[a.length / 2];

     15        int[] second = new int[a.length - first.length];

     16        // Copy the first half of a into first, the second half into second

     17        for (int i = 0; i < first.length; i++)

     18        {

     19           first[i] = a[i];

     20        }

     21        for (int i = 0; i < second.length; i++)

     22        {

     23           second[i] = a[first.length + i];

     24        }

     25        sort(first);

     26        sort(second);

     27        merge(first, second, a);

     28     }

     29

     30     /**

     31        Merges two sorted arrays into an array

     32        @param first the first sorted array

     33        @param second the second sorted array

     34        @param a the array into which to merge first and second

     35     */

     36     private static void merge(int[] first, int[] second, int[] a)

     37     {

     38        int iFirst = 0; // Next element to consider in the first array

     39        int iSecond = 0; // Next element to consider in the second array

     40        int j = 0; // Next open position in a

     41

     42        // As long as neither iFirst nor iSecond is past the end, move

     43        // the smaller element into a

     44        while (iFirst < first.length && iSecond < second.length)

     45        {

     46           if (first[iFirst] < second[iSecond])

     47           {

     48              a[j] = first[iFirst];

     49              iFirst++;

     50           }

     51           else

     52           {

     53              a[j] = second[iSecond];

     54              iSecond++;

     55           }

     56           j++;

     57        }

     58

     59        // Note that only one of the two loops below copies entries

     60        // Copy any remaining entries of the first array

     61        while (iFirst < first.length)

     62        {

     63           a[j] = first[iFirst];

     64           iFirst++; j++;

     65        }

     66        // Copy any remaining entries of the second half

     67        while (iSecond < second.length)

     68        {

     69           a[j] = second[iSecond];

     70           iSecond++; j++;

     71        }

     72     }

     73  }